import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/8/19
 * Time: 17:03
 */
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int lenW = words[0].length();
        int m = words.length;
        int lenS = s.length();
        List<Integer> result = new ArrayList<>();
        if (s.length() < lenW) {
            return result;
        }
        HashMap<String,Integer> map1 = new HashMap<>();
        //将words放入容器中
        for (String word : words) {
            map1.put(word, map1.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < lenW; i++) {//执行次数
            HashMap<String,Integer> map2 = new HashMap<>();
            for(int left = i,right = i,count = 0;right + lenW <= lenS; right += lenW) {
                String in  = s.substring(right,right + lenW);
                //入窗口
                map2.put(in, map2.getOrDefault(in, 0) + 1);
                if (map2.get(in) <= map1.getOrDefault(in, 0) && map2.get(in) > 0) {
                    count++;
                }
                while(right - left + 1 > lenW * m) {
                    //出窗口
                    String out = s.substring(left,left + lenW);
                    if(map2.get(out) <= map1.getOrDefault(out, 0)) {
                        count--;
                    }
                    map2.put(out, map2.get(out) - 1);
                    left += lenW;
                }
                if(count == words.length) {
                    result.add(left);
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> substring = solution.findSubstring("barfoothefoobarman", new String[]{"foo","bar"});
        for(Integer i: substring) {
            System.out.println(i);
        }
    }
}